import java.util.Scanner;

public class demo {
//  星际密码

//星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：
//n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
/*
set A=|1 1|  A^2=|2 1|  A^3=|3 2|  A^4=|5 3|  A^5=|8 5|
      |1 0|      |1 1|      |2 1|      |3 2|      |5 3|
事实上，实对称矩阵相乘仍然是实对称矩阵。观察易得，A^(n-1)由于左乘A（也可以右乘,此处举例左乘）
X1为上A^(n-1)的第一行元素相加 X2为A^(n-1)的第一个元素（左上角元素），由于对称X3和X2一样，
X4=A^(n-1)的第2个元素
迭代得到规律左上角元素X1[n]=X1[n-1]+X1[n-2] 为fb数列1 2 3 5 8
另外，不只是X1为此数列，其他所有元素都是这个数列
取4位只需%10000即可。
*/

    public static void main(String[] args) {
        int[] arr = new int[10001];
        arr[0] = 1;
        arr[1] = 1;
        for (int i=2; i<10001; i++) {
            arr[i] = arr[i-1] + arr[i-2];
            arr[i] = arr[i]%10000;
        }
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            StringBuffer sb = new StringBuffer();
            for (int i=0; i<n; i++) {
                int sum = in.nextInt();
//                String.format()字符串格式化
//                这里表示占4位空间 <4补0
                sb.append(String.format("%04d", arr[sum]));
            }
            System.out.println(sb);
        }
    }











//    数根(注意范围)
//数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，
//那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。
//再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。
//现在给你一个正整数，输出它的数根。
//输入描述:
//输入包含多组数据。
//每组数据数据包含一个正整数n（1≤n≤10E1000）。 注意这里是10^1000
//    求正整数n的树根，n的范围为[1, 10^1000]
//    int和long都不在取值范围内，此时要接收输入的数据，只能考虑以下类型:
//    (1) BigDecimal
//    (2) String
//题目要求是每一位来相加， 相对来说，使用String从0开始遍历以后相加更加容易

    //    要注意的事项:
//(1)相加后的结果可能还不是一位数， 即还不满足树根的要求，需要再次相加如759，则为7+5+9=21, 不是一位数，还需要再次计算: 2+1=3, 则树根为3
//(2)字符串可以使用charAt(int index)方法获取字符，字符可以直接转换为int特殊的，当字符是数字0-9时，
//可以使用字符与字符相减操作，即可得到数字的差值
//如'9'- '6'，返回值即为9-6的结果3
//所以字符'0'-"9', 要取int值，使用字符- '0'即可
//如字符'5'，要获取数字值5,使用5'-'0'即可
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            while (str.length() > 1) {
                int sum = 0;
                for (int i=0; i<str.length(); i++) {
                    sum += str.charAt(i) - '0';
                }
//                基本数据型态转换成 String
                str = String.valueOf(sum);
            }
            System.out.println(str);
        }
    }
}
